#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
long long A=1992919, B=18181971;
FILE *f;
char s[20];
int ts=1;
int next()
{
	A=(A*13166771+B)%1000000007;
	B=(B*67771+A)%1000000007;
	return A;
}
void createtest() { sprintf(s, "%03d", ts); ts++; f=fopen(s, "w"); }
#define N 100100
int u[N];
set <long long> w;
void shuffle(int *a, int n)
{
	int i, j;
	for(i=n; i>0; j=next()%i, swap(a[i-1], a[j]), i--);
}
void gen0()
{
	createtest();
	fprintf(f, "5 6\n1 2\n2 3\n3 5\n4 5\n1 5\n1 3\n");
	createtest();
	fprintf(f, "1 0\n");
	createtest();
	fprintf(f, "2 1\n2 1\n");
	createtest();
	fprintf(f, "3 3\n3 1\n1 2\n3 2\n");
	createtest();
	fprintf(f, "7 6\n1 2\n1 3\n1 4\n5 1\n6 1\n7 1\n");
	createtest();
	fprintf(f, "5 6\n1 2\n1 3\n1 4\n2 5\n3 5\n4 5\n");
}
void gen1(int n, int k)
{
	createtest();
	w.clear();
	int i, j;
	for(i=0; i<n; u[i]=i+1, i++);
	shuffle(u, n);
	for(fprintf(f, "%d %d\n", n, k); k; )
	{
		i=next()%n;
		j=next()%n;
		if(i==j) continue;
		if(j<i) swap(i, j);
		if(w.find((long long)i*N+j)!=w.end()) continue;
		w.insert((long long)i*N+j);
		fprintf(f, "%d %d\n", u[i], u[j]);
		k--;
	}
}
void gen2(int n, int k, int t)
{
	createtest();
	int i, j, l;
	for(i=0; i<n; u[i]=i+1, i++);
	shuffle(u, n);
	for(fprintf(f, "%d %d\n", n*t, k*t), l=k; t--; )
	{
		w.clear();
		for(k=l; k; )
		{
			i=next()%n;
			j=next()%n;
			if(i==j) continue;
			if(j<i) swap(i, j);
			if(w.find((long long)i*N+j)!=w.end()) continue;
			w.insert((long long)i*N+j);
			fprintf(f, "%d %d\n", t*n+u[i], t*n+u[j]);
			k--;
		}
	}
}
void gen3(int n)
{
	createtest();
	int i, k;
	k=3*(n/2-1);
	for(fprintf(f, "%d %d\n", n, k), i=0; i+2<n; i+=2)
	{
		fprintf(f, "%d %d\n", i+1, i+2);
		fprintf(f, "%d %d\n", i+2, i+3); 
		fprintf(f, "%d %d\n", i+1, i+3);
	}
}
void gen4(int n)
{
	createtest();
	int i, k;
	k=4*(n/3-1);
	for(fprintf(f, "%d %d\n", n, k), i=0; i+3<n; i+=3)
	{
		fprintf(f, "%d %d\n", i+1, i+2);
		fprintf(f, "%d %d\n", i+1, i+3); 
		fprintf(f, "%d %d\n", i+2, i+4);
		fprintf(f, "%d %d\n", i+3, i+4);
	}
}
void gen5(int n)
{
	createtest();
	int i, k;
	k=n-1;
	for(fprintf(f, "%d %d\n", n, k), i=1; i<n; i++)
		if(i%2) fprintf(f, "%d %d\n", 1, i+1);
		else fprintf(f, "%d %d\n", i+1, 1);
}
void gen6(int n)
{
	createtest();
	int i, k;
	k=2*(n-2);
	for(fprintf(f, "%d %d\n", n, k), i=2; i<n; fprintf(f, "%d %d\n%d %d\n", 1, i+1, i+1, 2), i++);
}
void gen7(int n)
{
	createtest();
	int i, k;
	k=n-1;
	for(fprintf(f, "%d %d\n", n, k), i=1; i<n; fprintf(f, "%d %d\n", i, i+1), i++);
}
void gen8(int n)
{
	createtest();
	int i, k;
	k=2*n-3;
	for(fprintf(f, "%d %d\n", n, k), i=1; i<n-1; fprintf(f, "%d %d\n%d %d\n", i, i+1, i, n), i++);
	fprintf(f, "%d %d\n", n-1, n);
}
void gen9(int n)
{
	createtest();
	int i, k;
	k=2*n-3;
	for(fprintf(f, "%d %d\n", n, k), i=2; i<n; fprintf(f, "%d %d\n%d %d\n", i, i+1, 1, i+1), i++);
	fprintf(f, "%d %d\n", 1, 2);
}
void gen10(int n)
{
	createtest();
	int i, k;
	k=n-1;
	for(fprintf(f, "%d %d\n", n, k), i=1; i<n; fprintf(f, "%d %d\n", i/2+1, i+1), i++);
}
int main()
{
	int i;
	gen0();
	for(i=0; i<10; i++)
		gen1(100, (i+1)*100);
	gen1(50000, 50000);
	gen1(20000, 50000);
	gen1(10000, 50000);
	gen1(5000, 50000);
	gen1(2000, 50000);
	gen1(1000, 50000);
	gen1(500, 50000);
	gen2(10, 10, 5000);
	gen2(10, 20, 2000);
	gen2(10, 30, 1000);
	gen2(50, 200, 200);
	gen3(25000);
	gen4(15000);
	gen5(50000);
	gen6(25000);
	gen7(50000);
	gen8(25000);
	gen9(25000);
	gen10(50000);
	return 0;
}